package a04_字符串;

/**
 * <p>
 * a06_实现strStr复习5
 * </p>
 *
 * @author flyduck
 * @since 2025/4/24
 */
public class a06_实现strStr复习5 {

    public static void main(String[] args) {
        a06_实现strStr复习5 test = new a06_实现strStr复习5();
        System.out.println(test.strStr("leetcode", "leeto"));
    }

    //aabaabaaf
    //aabaaf
    public int strStr(String haystack, String needle) {
        char[] bigChars = haystack.toCharArray();
        char[] smallChars = needle.toCharArray();
        int[] nextArray = getNextArray(smallChars);

        int smallIdx = 0;
        int bigIdx = 0;
        while (smallIdx < smallChars.length && bigIdx < bigChars.length){
            if(smallChars[smallIdx] == bigChars[bigIdx]){
                smallIdx++;
                bigIdx++;
            }else {
                smallIdx = nextArray[smallIdx];
                if(smallIdx == -1){
                    smallIdx = 0;
                    bigIdx++;
                }
            }
        }
        //9-6
        if(smallIdx == smallChars.length){
            return bigIdx - smallIdx;
        }else {
            return -1;
        }
    }

    private int[] getNextArray(char[] chars){
        if(chars.length == 1){
            return new int[]{-1};
        }

        int[] nextArray = new int[chars.length];
        nextArray[0] = -1;
        nextArray[1] = 0;

        // xxxaxxxab
        //        3
        //         如果chars[currentIdx - 1] == chars[compareIdx]，这里就等于compareIdx+1
        int currentIdx = 2;
        int compareIdx = nextArray[currentIdx - 1];
        while (currentIdx < chars.length){
            if(chars[currentIdx - 1] == chars[compareIdx]){
                nextArray[currentIdx] = compareIdx + 1;
                currentIdx++;
                compareIdx = nextArray[currentIdx - 1];
            }else {
                if(compareIdx == 0){
                    nextArray[currentIdx] = 0;
                    currentIdx++;
                    compareIdx = nextArray[currentIdx - 1];
                }else {
                    compareIdx = nextArray[compareIdx];
                }
            }
        }
        return nextArray;
    }
}
